//后缀表达式
//思路就是遇到数字入栈 遇到操作符取栈顶两个元素进行运算
class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int>st;
        for(int i=0;i<tokens.size();i++)
        {
            if(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*" ||tokens[i]=="/")
            {
                int numr=st.top();
                st.pop();
                int numl=st.top();
                st.pop();
                switch(tokens[i][0])
                {
                    case '+':
                        st.push(numr+numl);
                        break;
                    case '-':
                        st.push(numl-numr);
                        break;
                    case '*':
                        st.push(numl*numr);
                        break;
                    case '/':
                        st.push(numl/numr);
                        break;
                    default:
                        break;
                }
            }
            else
            {
                st.push(stoi(tokens[i]));
            }
        }
        return st.top();

    }
};

//不同的子序列
class Solution {
public:
    int numDistinct(string s, string t) 
    {
        //dp[i][j] s的前i个字符 出现t的前j个字符的数量
        //如果 s[i]==s[j]
        //dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
        int m=s.size()+1;
        int n=t.size()+1;
        vector<vector<uint64_t>>dp(m,vector<uint64_t>(n,0));
        dp[0][0]=1;
        for(int i=1;i<m;i++)
        {
            dp[i][0]=1;
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(s[i-1]==t[j-1])
                {
                    //1.使用s[i-1] 由于二者相同 
                    //带上这个字母出现t的次数 跟不带上是一样的
                    //=dp[i-1][j-1]
                    //2.不使用s[i-1]
                    //=dp[i-1][j]
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                }
                else
                {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

//填充每个节点的下一个右侧节点指针II
class Solution {
public:
    //思路是将每一层都当做一个链表
    //cur是上一层 phead是当前层的虚拟头结点 tmp是当前层的指针
    //一开始时 phead和tmp指向同一块空间 进行tmp->next=cur->left操作
    //也就是说 我需要往下走一层的时候 只需要拿到phead->next即可 
    Node* connect(Node* root) 
    {
        if(root==nullptr) return nullptr;
        Node*cur=root;
        while(cur!=nullptr)
        {
            //创建一个虚拟头结点 头结点的next指针指向cur的左树
            Node* phead=new Node(-1);
            Node* tmp=phead;
            //对于每一层的循环
            while(cur!=nullptr)
            {
                if(cur->left)
                {
                    tmp->next=cur->left;//phead->next也就等于cur->left了
                    tmp=tmp->next;
                }
                if(cur->right)
                {
                    tmp->next=cur->right;
                    tmp=tmp->next;
                }
                cur=cur->next;
            }
            //走到空了 说明当前层已经遍历完成了 需要开始遍历下一层了
            cur=phead->next; //刚好走到下一层
        }
        return root;
    }
};
//杨辉三角
class Solution {
public:
    vector<vector<int>> generate(int numRows)
    {
        vector<vector<int>> a;
        a.resize(numRows);
        for(size_t i=0;i<numRows;i++)
        {   
            //开辟空间
            a[i].resize(i+1,0);//第0行开一个... 用0初始化
            a[i].front()=a[i].back()=1;
        }
        //开始遍历
        for(size_t i=0;i<numRows;i++)
        {
            for(size_t j=0;j<a[i].size();j++)
            {
                if(a[i][j]==0)
                {
                    a[i][j]=a[i-1][j]+a[i-1][j-1];
                }
            }
        }
        return a;
    }
};
//每日温度
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) 
    {
        stack<int> st;//存的是下标
        vector<int>res(temperatures.size(),0);
        st.push(0);
        for(int i=0;i<temperatures.size();i++)
        {
            if(temperatures[i]<temperatures[st.top()])
            {
                st.push(i);
            }
            else
            {
                while(!st.empty() && temperatures[i]>temperatures[st.top()])
                {
                    res[st.top()]=i-st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return res;
    }
};

//直方图最大矩形面积
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) 
    {
        //思路：找到某一个高度的柱子，查到他右边第一个和左边第一个比它低的柱子
        //这样就确定了底边长，高就是这个柱子的高度 这样就可以用来算面积。
        //找右边第一个比自己低的可以使用单调栈，而且左边第一个比自己低的就是栈顶的下一个元素
        //所以是大于栈顶元素就入栈
        //发现，每进行一次运算需要三个元素 左边第一个比自己低的 自己 和右边第一个比自己低的
        //如果第二个元素就比第一个元素大，那么如何计算？
        //如果某一个元素的右边所有元素都比自己大，又如何走到计算面积的逻辑？
        //所以需要在heights数组中头插和尾插一个0
        if(heights.empty()) return 0;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        int res=0;
        stack<int> st;//里面存的是数组下标
        st.push(0);
        for(int i=1;i<heights.size();i++)
        {
            if(heights[i]>=heights[st.top()])
            {
                st.push(i);
            }
            else
            {
                while(!st.empty() && heights[i]<heights[st.top()])
                {
                    int midindex=st.top();
                    st.pop();
                    int leftindex=st.top();
                    res=max(res,(i-leftindex-1)*heights[midindex]);
                }
                st.push(i);
            }
        }
        return res;
    }
};
//矩阵中最大的矩形
class Solution {
public:
    int maximalRectangle(vector<string>& matrix) 
    {
        if(matrix.empty()) return 0;
      
        //题目是39的进阶。39是一组数据让求最大矩形面积，而这里是一个矩阵
        //矩阵中最大的矩形一定是以某一行为底开始计算的
        //所以也就是说如果我们可以将每一行都进行39题的过程，那这个问题也就
        //解决了。

        //那么如何将矩阵转换为39题的vector呢？
        //对于每一列col，从matrix[row][col]开始
        //向上统计有多少个连续的1 统计结果作为直方图高度 
        //1 0 1 0 0   以第一行为底则数组为 1 0 1 0 0
        //1 0 1 1 1   以第二行为底则数组为 2 0 2 1 1
        //0 1 1 1 1   以第三行为底则数组为 0 1 3 1 1
        int m=matrix.size();
        int n=matrix[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        for(int i=0;i<n;i++)
        {
            dp[0][i]=matrix[0][i]=='0'?0:1;
        }
        for(int i=1;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                dp[i][j]=matrix[i][j]=='0'?0:dp[i-1][j]+1;
            }
        }
        int res=0;
        for(int i=0;i<m;i++)
        {
            vector<int>tmp=dp[i];
            tmp.insert(tmp.begin(),0);
            tmp.push_back(0);
            stack<int> st;//里面存的是数组下标
            st.push(0);
            for(int i=1;i<tmp.size();i++)
            {
                if(tmp[i]>=tmp[st.top()])
                {
                    st.push(i);
                }
                else
                {
                    while(!st.empty() && tmp[i]<tmp[st.top()])
                    {
                        int midindex=st.top();
                        st.pop();
                        int leftindex=st.top();
                        res=max(res,(i-leftindex-1)*tmp[midindex]);
                    }
                    st.push(i);
                }
            }
        }
        return res;
    }
};
//最小路径之和
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        dp[0][0]=grid[0][0];
        for(int i=1;i<n;i++)
        {
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for(int i=1;i<m;i++)
        {
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

//三角形中最小路径之和
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) 
    {
        if(triangle.empty()) return 0;
        vector<vector<int>>dp(triangle.size());
        for(int i=0;i<triangle.size();i++)
        {
            dp[i].resize(triangle[i].size(),0);
        }
        dp[0][0]=triangle[0][0];
        for(int i=1;i<triangle.size();i++)
        {
            dp[i][0]=dp[i-1][0]+triangle[i][0];
        }
        for(int i=1;i<triangle.size();i++)
        {
            for(int j=1;j<triangle[i].size();j++)
            {
                if(j==triangle[i].size()-1)
                {
                    dp[i][j]=dp[i-1][j-1]+triangle[i][j];
                }
                else
                {
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
                }
            }
        }
        int res=INT_MAX;
        for(int i=0;i<dp[triangle.size()-1].size();i++)
        {
            res=min(res,dp[triangle.size()-1][i]);
        }
        return res;
    }
};

//分割等和子集
class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        int sum=0;
        for(auto e:nums) sum+=e;
        if(sum%2!=0) return false;
        int target=sum/2;
        //一个背包能否恰好能装下总和一半的东西
        vector<int>dp(10001,0);
        for(int i=0;i<nums.size();i++)
        {
            for(int j=target;j>=nums[i];j--)
            {
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if (dp[target] == target) return true;
        return false;
    }
};